#include <stdio.h>
#include <stdlib.h>
#include "stack.h"
#include "queue.h"

// "queue.h" eight function:
LinkQueue createEmptyQueue_link(void);
Bool isEmptyQueue_link(LinkQueue Q);
DataType_s_q frontQueue_link(LinkQueue Q);
void enQueue_link(LinkQueue Q, DataType_s_q x);
void deQueue_link(LinkQueue Q);
LinkQueue createLinkQueue_H(void);
void print_queue(LinkQueue Q);
void destroy_queue(LinkQueue Q);

// "stack.h" six functions:
PLinkStack createEmptyStack_link(void);
Bool isEmptyStack_link(PLinkStack plstack);
Bool Stack_is_full(PLinkStack plstack);
void push_link(PLinkStack plstack, DataType_s_q x);
void pop_link(PLinkStack plstack);
DataType_s_q top_link(PLinkStack plstack);

// binary-tree nine functions:
Bool isEmptyTree_link(BinTree bt);
void PreOrder(BinTree t);
void InOrder(BinTree t);
void PostOrder(BinTree t);
void InOrder_2(BinTree t);
void LevelOrder(BinTree bt);
void leaf(BinTree BT);
int leaf_2(BinTree bt);
BinTree Search(BinTree bt, DataType x);
int BinTreeDepth_2(BinTree bt);
BinTree createBinTree(BinTree p);



// 时间，空间都是O(1).
Bool isEmptyTree_link(BinTree bt)
{
        return bt == NULL;
}

// 递归写法的前、中、后序遍历本质其实都是DFS，DFS隐式的维护了一个栈，
// 而不用人为去创建再去维护，所有空间复杂度就是常数级.
// 时间复杂度：O(N)，因为要遍历所有节点。
// 空间复杂度： O(1).
void PreOrder(BinTree t)
{
        if (!t) {
                return ;
        }
        printf("%d ", t->val);
        PreOrder(t->left);
        PreOrder(t->right);
}

// 时间复杂度：O(N)，因为要遍历所有节点。
// 空间复杂度： O(1).
void InOrder(BinTree t)
{
        if (!t) {
                return ;
        }
        InOrder(t->left);
        printf("%d ", t->val);
        InOrder(t->right);
}

// 时间复杂度：O(N)，因为要遍历所有节点。
// 空间复杂度： O(1).
void PostOrder(BinTree t)
{
        if (!t) {
                return ;
        }
        PostOrder(t->left);
        PostOrder(t->right);
        printf("%d ", t->val);
}

// 这里的中序遍历采用非递归的写法，因为使用了栈，所以空间复杂度为O(N).
// 时间复杂度：O(N)，因为要遍历所有节点。
// 空间复杂度： O(N)，使用了栈，需要把所有节点加入栈.
void InOrder_2(BinTree t)
{
        BinTree bt;
        PLinkStack s = createEmptyStack_link();
        bt = t;
        while (bt || !isEmptyStack_link(s)) {
                while (bt) {
                        push_link(s, bt);
                        if (bt->left != NULL) {
                                bt = bt->left;
                        } else {
                                break;
                        }
                }
                bt = top_link(s);
                pop_link(s);
                printf("%d ", bt->val);
                bt = bt->right;
        }
}

// 时间复杂度：O(N)，因为要遍历所有节点.
// 空间复杂度： O(N)，使用了队列，需要把所有节点加入队列.
void LevelOrder(BinTree bt)
{
        LinkQueue q;
        if (!bt) return ;
        q = createEmptyQueue_link();
        // 先将根节点的值入队.
        enQueue_link(q, bt);
        while (!isEmptyQueue_link(q)) {
                // 获得队首元素后并将其出队.
                bt = frontQueue_link(q);
                deQueue_link(q);
                printf("%d ", bt->val);
                if (bt->left) enQueue_link(q, bt->left);
                if (bt->right) enQueue_link(q, bt->right);
        }
}

// 后序遍历统计叶子结点的个数.
int n = 0;
void leaf(BinTree BT)
{
        if (!BT) return ;
        // 若该结点左右子树都不存在就为叶子结点.
        if (!BT->left && !BT->right) {
                n++;
        }
        leaf(BT->left);
        leaf(BT->right);
}

// 分治法统计叶子节点个数.
// 二叉树所有节点的个数为N.
// 时间复杂度：O(N)，因为需要遍历所有节点.
// 空间复杂度：O(N)，和递归深度有关，因为当树退化为链表时，递归深度可达N.
int leaf_2(BinTree bt)
{
        int count;
        // 如果是空树那么叶子节点的个数为0.
        if (isEmptyTree_link(bt)) return 0;
        // 如果是叶子节点，那么统计数量加一.
        else if (bt->left == NULL && bt->right == NULL) {
                return 1;
        }
        // 如果当前节点不是叶子节点，那么就分别寻找当前节点左子树的叶子节点数量
        // 和右子树的叶子节点的数量，然后再相加得到当前以当前节点为根节点的叶子节点的数量.
        else {
                count = leaf_2(bt->left) + leaf_2(bt->right);
        }
        return count;
}

// 在二叉树bt中查找元素x.
// 树的结点数为N.
// 时间复杂度：O(N),最坏情况下遍历树的所有结点.
// 空间复杂度：O(N),和递归的深度有关，若树退化为斜二叉树，递归深度可达N.
// 感觉就是用先序遍历在寻找值为x的结点.
BinTree Search(BinTree bt, DataType x)
{
        if (!bt) return NULL;
        BinTree p;
        if (bt->val == x) return bt;
        if (bt->left) {
                p = Search(bt->left, x);
                if (p) return p;
        }
        if (bt->right) {
                p = Search(bt->right, x);
                if (p) return p;
        }
        return NULL;
}

// 利用后续遍历来实现深度的求解.
// n为树结点的数量.
// 时间复杂度：O(n),因为要遍历树的每个结点
// 空间复杂度：O(n),因为在最坏情况下二叉树退化为斜二叉树，递归深度可达到n.
int BinTreeDepth_2(BinTree bt)
{
        int depth;
        // terminal
        if (bt == NULL) return 0;
        // process current logic
        int left_depth = BinTreeDepth_2(bt->left) + 1;
        int right_depth = BinTreeDepth_2(bt->right) + 1;
        // drill down
        depth = left_depth > right_depth ? left_depth : right_depth;
        return depth;
}

// 中序遍历创建二叉树.
// 时间复杂度：O(N)，因为要把所有节点建立起来.
// 空间复杂度：O(1).
BinTree createBinTree(BinTree p)
{
        int c;
        scanf("%d", &c);
        if (c == FLAG) return NULL;
        else {
                p = (BinTree)malloc(sizeof(struct BinTreeNode));
                if (p == NULL) {
                        printf("Out of memory.Can't malloc a BinTreeNode.\n");
                        return p;
                }
                p->val = c;
                p->left = createBinTree(p->left);
                p->right = createBinTree(p->right);
        }
        return p;
}

int main()
{
        BinTree bt;
        bt = createBinTree(bt);
        if (isEmptyTree_link(bt)) {
                printf("The tree is an empty tree.\n");
                goto FLAG1;
        } else {
                printf("The tree is not an empty tree.\n");
        }
        printf("PreOrder: \n");
        PreOrder(bt);
        printf("\n");
        printf("InOrder: \n");
        InOrder(bt);
        printf("\n");
        printf("PostOrder: \n");
        PostOrder(bt);
        printf("\n");
        printf("InOrder_2: \n");
        InOrder_2(bt);
        printf("\n");
        printf("LevelOrder: \n");
        LevelOrder(bt);
        printf("\n");
FLAG1:
        leaf(bt);
        printf("The tree leaf numbers is %d\n", n); // n是全局变量.
        printf("The tree leaf_2 numbers is %d\n", leaf_2(bt));
        int x;
        printf("Please input a number to search: ");
        scanf("%d", &x);
        BinTree tmp = Search(bt, x);
        if (tmp != NULL) {
                printf("the search number is: %d\n", tmp->val);
        } else {
                printf("Can't find current number.\n");
        }
        printf("The current tree's depth is %d\n", BinTreeDepth_2(bt));
        return 0;
}
